package tree;

import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description: 112. 路径总和
 * User: Li_yizYa
 * Date: 2025/6/3
 * Time: 22:24
 */
public class Solution21 {
    /**
     * 递归写法
     * @param root
     * @param targetSum
     * @return
     */
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        if (root.left == null && root.right == null) {
            return root.val == targetSum;
        }
        return hasPathSum(root.left, targetSum - root.val) ||
                hasPathSum(root.right, targetSum - root.val);
    }

    /**
     * 非递归（基于栈）
     * @param root
     * @param targetSum
     * @return
     */
    public boolean hasPathSum1(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();

        stack1.push(root);
        stack2.push(root.val);

        while (!stack1.isEmpty()) {
            int len = stack1.size();
            while (len > 0) {
                len--;
                TreeNode node = stack1.pop();
                int sum = stack2.pop();
                if (node.left == null && node.right == null && sum == targetSum) {
                    return true;
                }
                if (node.left != null) {
                    stack1.push(node.left);
                    stack2.push(node.left.val + sum);
                }
                if (node.right != null) {
                    stack1.push(node.right);
                    stack2.push(node.right.val);
                }
            }
        }

        return false;
    }
}
